package 华为机试;

import java.util.*;

/**
 * Created by BinLee on 2017/8/3.
 */
public class 归并排序最简单版本 {
    public static void main(String[] args) {
        int[] b = new int[]{4, 3, 6, 1, 2, 5, -10, 100, -99, 1000};
        System.out.println(Arrays.toString(b));
        mergeSort_toDown(b, 0, b.length - 1);
        System.out.println(Arrays.toString(b));
    }

    private static void mergeSort_toDown(int[] a, int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            mergeSort_toDown(a, l, m);
            mergeSort_toDown(a, m + 1, r);
            merge(a, l, m, r);
        }
    }

    private static void merge(int[] a, int l, int m, int r) {
        int[] tmp = new int[r - l + 1];
        int i = l, j = m + 1, idx = 0;
        while (i <= m && j <= r)
            tmp[idx++] = a[i] <= a[j] ? a[i++] : a[j++];
        while (i <= m)
            tmp[idx++] = a[i++];
        while (j <= r)
            tmp[idx++] = a[j++];
        System.arraycopy(tmp, 0, a, l, tmp.length);
    }

}
